﻿#pragma once

#include <iostream>

using namespace std;

#define WSETSIZE 50
template <typename T>
class WSet {
public:
    WSet(){
       m_dataList = new T[WSETSIZE];
       m_usedFlag = new bool[WSETSIZE];
       for(int i = 0; i < WSETSIZE; i++) {
           m_usedFlag[i] = false;
       }
       m_count = 0;
    }

    virtual ~WSet() {
       delete [] m_dataList;
       delete [] m_usedFlag;
    }

    void insert(T value) {
       int loc = hash(value);
       while (m_usedFlag[loc]) {
           if (m_dataList[loc] == value) { // 若有重复数据，则直接不处理，这是QSet可以去重的关键
               // m_list.push_back(value); // 这个地方若再用list接收重复数据，则是QMultiHash
               return;
           }
           loc = (loc + 1) % WSETSIZE;
       }
       m_usedFlag[loc] = true;
       m_dataList[loc] = value; // 若这里放的不是value，而是一个结构体，那么就可以形成key-value类型的QHash容器
       m_count++;
    }

    // 不同的平台实现方式是不一样的，有些平台是直接返回m_count，有些是遍历一遍，所以size函数也不一定是线程安全的
    int size() {
        // return m_count;
        int res = 0;
        for(int i = 0; i < WSETSIZE; i++) {
            if (m_usedFlag[i]) {
                res++;
            }
        }
        return res;
    }

    void remove(T value) {
//        for(int i = 0; i < HASHSIZE; i++) {
//            if (m_dataList[i] == value) {
//                m_usedFlag[i] = false;
//            }
//        }
        int loc = hash(value);
        while (m_usedFlag[loc]) {
            if (m_dataList[loc] == value) {
                m_usedFlag[loc] = false;
                m_count--;
                break;
            } else {
                loc = (loc + 1) % WSETSIZE;
            }
        }
    }

    // 这里表面提供的是输入value，返回value无用的函数。但是若输入value是QHash的key，m_dataList[loc]若是个包含value值的结构体，
    // 那么返回值就可以类似QHash的value值，这里实际是提供了QHash的取值原理
    T getValue(T value)
    {
        int loc = hash(value);
        while (m_usedFlag[loc]) {
            if (m_dataList[loc] == value) {
                return m_dataList[loc];
            } else {
                loc = (loc + 1) % WSETSIZE;
            }
        }
    }

    void clear() {
        for(int i = 0; i < WSETSIZE; i++) {
           m_usedFlag[i] = false;
        }
    }

    void printAll() {
        for(int i = 0; i < WSETSIZE; i++) {
            if(m_usedFlag[i]) {
               cout << m_dataList[i] << " ";
            }
        }
        cout << endl;
    }
private:
    T *m_dataList = nullptr;
    bool *m_usedFlag;
    int m_count = 0;

    int hash(T key) { // 返回的hash值与key的值相关，与数据的插入顺序无关，这样就造成了QSet的无序性
        return key % WSETSIZE; // 求余留数法取hash
    }
};

